The Grammar of Membership
Unlike ordered pairs $(a, b)$ or $n$-tuples where position is paramount, a set $\{a, b\}$ is defined exclusively by its elements. Thus, $\{a, b\} = \{b, a\}$. This indifference to sequence allows us to focus on the identity of membership.
An inclusion $A \subseteq B$ implies every element of $A$ resides within $B$. However, a proper subset $A \subset B$ demands more: $B$ must contain at least one element that is not in $A$.
The Power Set $\mathcal{P}(S)$ is the set of all possible subsets of $S$. If $|S| = n$, then $|\mathcal{P}(S)| = 2^n$, mapping the exponential scale of foundational possibilities.
The Logical Bridge: Set Mechanics
Set operations are the physical manifestations of logical thoughts:
- Union ($A \cup B$): The logical OR. Elements belonging to $A$ or $B$.
- Intersection ($A \cap B$): The logical AND. Elements belonging to both $A$ and $B$.
- Disjoint Sets ($A \cap B = \emptyset$): Mutually exclusive logical conditions.
Worked Example: The Student Database
Consider a database $D_1 = \{\text{Garth, Erin, Marty}\}$. We define two predicates:
- Set $A$: Students over 5'10" $\to \{\text{Garth, Marty}\}$.
- Set $B$: Students with names ending in 'y' $\to \{\text{Marty}\}$.
The Intersection $A \cap B$ yields $\{\text{Marty}\}$. This demonstrates how the logical "AND" filters a population based on overlapping criteria. Marty is the only student who satisfies both being tall and having a name ending in 'y'.
$x \in A \cap B \iff (x \in A) \land (x \in B)$